/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/set-matrix-zeroes
   @Language: C++
   @Datetime: 16-02-09 08:31
   */

class Solution {
public:
	/**
	 * @param matrix: A list of lists of integers
	 * @return: Void
	 * tips: the original zero can effact current row and col,
	 *       but the new zero has no effact, so the original
	 *       zero has factor for zero, we call it zero factor.
	 * select one row and one col to store the zero factors,
	 * and set zeros according to the factors.
	 * sketch: (origin)        O is factor         result
	 *      *  *  *  0         *  O  O  0        0  0  0  0
	 *      *  0  *  *  --->   *  0  *  O  --->  0  0  0  0
	 *      *  *  0  *         *  *  0  O        0  0  0  0
	 *      *  *  *  *         *  *  *  *        *  0  0  0
	 *  using first zero row=0 and col=3 to store zero factors
	 * 
	 */
	void setZeroes(vector<vector<int> > &mat) {
		// write your code here
		if (mat.size()<1 || mat[0].size()<1) return;
		int m=mat.size(), n=mat[0].size(), row=-1, col=-1;
		for (int i=0; i<m; ++i){
			for (int j=0; j<n; ++j){
				if (mat[i][j] != 0) continue;
				if (row==-1) row = i, col = j;	// select this row and col
				mat[i][col] = 0;		// to store the zero factor
				mat[row][j] = 0;		// to store the zero factor
			}
		}
		if (row==-1) return;
		for (int i=0; i<m; ++i){
			if (i == row) continue;		// set zero except row
			for (int j=0; j<n; ++j){
				if (j == col) continue;	// set zero except col
				if (mat[row][j]==0 || mat[i][col]==0) mat[i][j]=0;
			}
		}
		for(int i=m; i; mat[--i][col]=0);	// set zero for row
		for(int j=n; j; mat[row][--j]=0);	// set zero for col
	}
};
